package com.liuyubo.sort;

import java.util.Arrays;

public class InsertionSort implements Sort {
    @Override
    public void sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int e = arr[i];
            int j;
            for (j = i; (j > 0 && e < arr[j - 1]); j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = e;
        }
    }

    @Override
    public String getName() {
        return "Insertion Sort";
    }

    public static void insertionSort(int[] arr, int l, int r) {
        for (int i = l + 1; i <= r; i++) {
            int e = arr[i];
            int j;
            for (j = i; j > l && arr[j - 1] > e; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = e;
        }
    }

    public static void main(String[] args) {
        int[] arr = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        InsertionSort sort = new InsertionSort();
        sort.sort(arr);
        Arrays.stream(arr).forEach(System.out::println);
    }
}
